package org.hegang.algorithm.selectionsort;

/**
 * @ClassName SelectionSort
 * @Describe: 选择排序
 * @Author: gang.he
 * @Email: SmileSkylife@outlook.com
 * @Date: Created in 21:42 2019/7/3
 * @Modified_By: TODO
 * @Version: V1.0
 */
public class SelectionSort {
    /**
     * 选择排序，选出最小的数，排到最前面
     * 每一轮循环必定选出一个
     *
     * @param arrays
     */
    public static void selectionSort(int[] arrays) {
        if (arrays == null || arrays.length == 0) {
            return;
        }
        for (int i = 0; i < arrays.length; i++) {
            int minValue = arrays[i];
            for (int j = i + 1; j < arrays.length; j++) {
                if (arrays[j] < minValue) {
                    minValue = arrays[j];
                    int temp = arrays[i];
                    arrays[i] = arrays[j];
                    arrays[j] = temp;
                }
            }
        }
    }

    /**
     * 易于理解的写法
     *
     * @param arrays
     */
    public static void _selectionSort(int[] arrays) {
        if (null == arrays || arrays.length == 0) {
            return;
        }
        for (int i = 0; i < arrays.length; i++) {
            // 最小值的索引坐标
            int min_index = i;
            // 最小值
            int min_value = arrays[i];
            // 一轮循环结束，必定找到一个最小值
            for (int j = i + 1; j < arrays.length; j++) {
                if (arrays[j] < min_value) {
                    min_value = arrays[j];
                    min_index = j;
                }
            }
            // 如果最小值索引坐标不等于初始值，则发现最小值，否则最小值就是当前循环第一个元素
            if (min_index > i) {
                int temp = arrays[i];
                arrays[i] = min_value;
                arrays[min_index] = temp;
            }
        }
    }

    /**
     * 优化的写法
     *
     * @param arrays
     */
    public static void optimizationSelectionSort(int[] arrays) {
        if (null == arrays || arrays.length == 0) {
            return;
        }
        for (int i = 0; i < arrays.length; i++) {
            // 最小值的索引坐标
            int min_index = i;
            // 一轮循环结束，必定找到一个最小值
            for (int j = i + 1; j < arrays.length; j++) {
                if (arrays[j] < arrays[min_index]) {
                    min_index = j;
                }
            }
            // 如果最小值索引坐标不等于初始值，则发现最小值，否则最小值就是当前循环第一个元素
            if (min_index > i) {
                int temp = arrays[i];
                arrays[i] = arrays[min_index];
                arrays[min_index] = temp;
            }
        }
    }
}
